package leetcode.editor.cn;

//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
//
// 示例 2：
//
//
//输入：nums = [0,1]
//输出：[[0,1],[1,0]]
//
//
// 示例 3：
//
//
//输入：nums = [1]
//输出：[[1]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 6
// -10 <= nums[i] <= 10
// nums 中的所有整数 互不相同
//
//
// Related Topics 数组 回溯 👍 3038 👎 0

import java.util.ArrayList;
import java.util.List;

//Java：全排列
public class Permutations{
    public static void main(String[] args) {
        Solution solution = new Permutations().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

        public   List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> cur = new ArrayList<>();
            backtracking(res, cur, nums);
            return res;
        }

        /**
         *
         * @param res 返回的结果集
         * @param cur 当前排列结果
         * @param nums 待排列元素
         */
        private   void backtracking(List<List<Integer>> res, List<Integer> cur, int[] nums) {
            // 终止条件
            if (cur.size() == nums.length) {
                res.add(new ArrayList<>(cur));//此时注意必须要新创建一个list，否则公用一个cur对象，会出错
            }
            // 处理逻辑
            for (int i = 0; i < nums.length; i++) {//for循环回溯元素
                if (!cur.contains(nums[i])) {
                    cur.add(nums[i]);//处理节点，表示当前节点加入排列结果中
                    backtracking(res, cur, nums);//递归调用
                    cur.remove(cur.size() - 1);//撤销节点，表示当前节点从排列结果中移除，回溯使用
                    /**
                     * 理解：
                     * 比如   已经排列 1，2 ，循环到3，
                     * 把3加入排列结果中，然后递归调用（触发终止条件返回），
                     * 撤销排列 3，函数结束，在返回上一个调用 。此时应该是调用2，待排列是1，2   2已经加入了
                     * 撤销2，变成排列1，遍历到3，cur不包含3（因为上一次已经撤销了），排列1，3，继续递归调用
                     */
                }
            }
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
